486D - Valid Sets - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
long long MOD;
int a[2005];
long long dp[2005];
int visited[2005];
int d;
vector<int> graph[2005] ;

void dfs(int current, int root){
    visited[current] = 1;
    for(auto u: graph[current]){
        if(visited[u] == 1){
            continue;
        }
        if(a[u] < a[root] || a[u] > a[root]+d){
            continue;
        }
        if((a[u] == a[root]) && u < root){
            continue;
        }
        dfs(u, root);
        dp[current] = dp[current]*(dp[u] + 1);
        dp[current] %= MOD;
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    MOD = 1e9+7;
    int n;
    cin>>d>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    for(int i=1; i<n; i++){
        int u, v;
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    long long res = 0;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            visited[j] = 0;
            dp[j] = 1;
        }
        dfs(i, i);
        res += dp[i];
        res %= MOD;
    }
    cout<<res;
    return 0;
}